package com.zbcn.structure;

/**
 * @description: 堆
 * @author likunn
 * @date 2024/8/14 13:58
 * @version 1.0
 */
public class ZbcnHeap {


    /**
     * 存储元素的容器
     */
    private int[] a;

    /**
     * 能存放的最大元素数量
     */
    private int max;

    /**
     * 当前存储的元素数量
     */
    private int count;

    /**
     * 初始化一个堆
     * @param capacity
     */
    public ZbcnHeap(int capacity) {
        this.a = new int[capacity + 1];
        this.max = max = capacity;
        this.count = count = 0;
    }


    /**
     * 核心思想：从下往上 堆化
     * @param data
     * @return
     */
    public boolean insert(int data){
        if (count >= max){
            System.out.println("堆满了不能再插入数据了");
            return false;
        }
        // command  很重要的一个知识点： 数组中，索引为 i
        // 左子树 的索引为 为 2*i； 右子树 的索引为  2*i +1 ，父节点索引 为 2/i
        // 计数+1，准备插入
        ++count;
        a[count] = data;

        int i = count;
        //堆化 i/2 > 0 表示存在父节点
        while(i/2 > 0 && a[i] > a[i/2]){

            // 交换位置
            int temp = a[i/2];
            a[i/2] = a[i];
            a[i] = temp;
            // 当前值设置为父节点
            i = i/2;
        }
        return true;
    }

    /**
     * 实现技巧：为了满足 堆的特性，堆为一颗完全二叉树，我们将堆中的最后一个元素放到堆顶，然后再从上往下堆化（父子节点比较，然后依据条件交换位置）
     * 核心：从上往下堆化
     * 完全二叉树 在数组中的存储特性 ， i = 1  存储的是树的根节点，及 堆顶元素
     * @return
     */
    public boolean  deletePieTop(){
        if (count <= 0){
            System.out.println("堆中没有元素了");
            return  false;
        }

        // 将堆中的最后一个元素放到堆顶
        a[1] = a[count];
        count --;

        //自上而下堆化
        int i = 1;
        int maxPoint = i;
        while (true){
            // 找出最大的子节点
            if (2*i < max && a[i] < a[2*i]){
                maxPoint = 2*i;
            }
            if (2*i+1 < max && a[maxPoint] < a[2*i+1]){
                maxPoint = 2*i+1;
            }
            //循环终止条件，当前位置不用交换了
            if (i == maxPoint) {
                break;
            }
            // 交换位置
            int temp = a[i];
            a[i] = a[maxPoint];
            a[maxPoint] = temp;

            i = maxPoint;
        }
        return true;
    }


    /**
     * 是从后往前处理数组，并且每个数据都是从上往下堆化。
     * @param a
     * @param n
     */
    public void buildHeap(int[] a, int n){
        for (int i = n/2; i > 1; i --){
            heapify(a,n,i);
        }

    }

    private void heapify(int[] a, int n, int i) {
        while (true){

            int maxPoint = i;
            // 循环结束的条件是，最大 的值就是 i 指定的索引
            if (i*2 < n && a[i] < a[i*2]){
                maxPoint = i*2;
            }
            if (i*2+1 < n && a[maxPoint] < a[i*2+1]){
                maxPoint = i*2+1;
            }
            if (i == maxPoint){
                break;
            }
            // 交换位置
            int temp = a[i];
            a[i] = a[maxPoint];
            a[maxPoint] = temp;

            // 符值索引
            i = maxPoint;
        }
    }

    /**
     * 排序思路：
     * 1. 将数组创建为堆
     * 2. 利用 堆来排序：
     * 2.1   按照大顶堆的特性，数组的 第 1 个元素就为数组的最大元素
     * 2.2 将 第一个元素 与数组的最后一个  元素（索引在n 位置） 交换位置
     * 2.3 对前面的 n-1 个元素再进行堆化
     * 2.4 再将堆化后的大顶堆 的第1 个元素 与 n-1 位置的元素 交换位置
     * 2.5 依次往下，直到将数组的只剩下一个元素就结束
     *
     * @param a
     */
    public void heapSort(int[] a){
        buildHeap(a,a.length);

        //将第一个 元素与最后一个元素交换位置
        for (int i = a.length-1; i > 1;i--){
            int temp = a[1];
            a[1] = a[i];
            a[i] = temp;
            i--;
            heapify(a,i,1);
        }



    }
}
